博弈论 1[入门] | 无糖乌龙

注意标号只是表示我是先加的哪个题.
③[luogu 3150] pb的游戏
原题链接:luogu 3150 pb的游戏
题目大意:一开始有一个数,每个人可以先把这个数拆成两个非零的整数,两者的和要等于原来的数,之后由对手丢弃掉其中的一个数,剩下的一个数给对手继续操作.直到有一个人无法再分割数字为止,不能分割的人输.问是否是先手必胜的,如果是输出pb wins如果不是则输出zs wins.
数据范围:
$1 < n < 50$

样例输入:

样例输出:

zs wins
zs wins
zs wins
pb wins
zs wins

这个题就是一个很典型的博弈论模型了,我们来考虑一下这个题的突破口在哪里.这个游戏,很显然必败态是数字为 $1$ 的时候,就没法进行操作了,继续往上推,可以发现 $2$ 就是一个必胜态,因为必然分割出两个 $1$ ,使对手走到 $1$ 上去.再然后,我们就可以推出本题的结论了:奇数必败,偶数必胜.
具体是为什么,下面来说明一下:这场游戏的过程中每个人肯定都是尽量构造出 $1$ 来的,但是对手一定是不会去选 $1$ 的,他肯定会选另外一个数.那么当先手手上的是偶数的时候,他就可以让对手手上的数字是奇数,如果对手手上的数字是一个奇数的话,那么一个奇数的状态只有可能是偶数和一个奇数的和,那么先手的人永远都可以选择偶数,即手上是偶数的人,通过合理的策略,可以使他手上的数永远是偶数,并最终达到 $2$ 这个必胜态.因此,先手手上的是偶数的人必胜.
这个游戏的关键就是,手上是偶数的人,拥有这个游戏的决定权,他可以让手上的数永远都是偶数而不是奇数.而手上是奇数的人不管怎样操作都必然会让对手得到一个偶数.这个不公平的形式,在之后的一道[codeforces 1382 B]里会再次提到.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		if(n & 1)	puts("zs wins");
		else puts("pb wins");
    }
    return 0;
}

①[POJ2484] A Funny game
原题链接：http://poj.org/problem?id=2484
题目大意： $n$ 个石头排成一圈，Alice和Bob轮流从圈里面抽石头，每次可以抽 $1$ 个或连续的 $2$ 个，抽完之后会留下空隙，空隙不会自动补上视为不连续。不能操作的人输。问Alice是否先手必胜。
数据范围： $1 \leq n \leq 10^6$

首先数据范围是很大的，搜索或者 $dp$ 的复杂度做不了，后者不行是因为这个状态的走法肯定不是单纯能线性解决的。要考虑挖掘题目性质，在博弈论题目中比较重要的一个想法就是看有没有什么策略构造出一个给对手的必败态。在具体考虑一个局面的时候，镜像操作是一个非常有利的操作手段，可以根据这个来构造。
假如场上已经分成了完全相同的两组石块。如下图：
则可以把两个石块和一个石块划分成一组，这个时候，假如这个局面丢给了对手，则A不管怎么操作只要镜像操作就一定胜利。也就是说如果构造出了一种分成两组且完全相同的局面，则对手一定是必败态，而A就一定是先手必胜了。
现在来考虑如何构造出这种特殊局面，不过在这之前，有个特殊情况需要判断： $n$ 在小于等于 $2$ 的时候是先手必胜毫无疑问的，先把这个边角情况抠出来再考虑整体的大范围情况，否则容易疏漏。
其次，在第一步之后，整个环会变成一个 $n-1$ 或 $n-2$ 长的链，这个时候B可以考虑奇数和偶数情况，使留下来的局面恰好是之前所说的两组相同的局面，导致A必输。具体来说，如果当前的链长度是奇数，就抽 $1$ 个，使环断成两个相同长度的，偶数同理。这说明如果A不是第一次就取完了所有状态，就一定必输。
结论： $n \leq 2$ 时A必胜，其余B必胜。

②[POJ 2348] Euclid's game
原题链接：http://poj.org/problem?id=2348
题目大意：给定了两个正整数 $a$ 和 $b$ ，规定每个人操作时可以从较大者中删去较小者的若干倍，至少是一倍。Stan先手，在自己的回合把其中一个数变成 $0$ 的一方获胜，问谁会获胜。
数据范围： $a$ 和 $b$ 都是正整数。

由于范围可能非常大（在 $int$ 范围内跑满可以到1e9往上），所以这个题从复杂度上来说可能是 $O(1)$ 或者最多 $log$ 或根号的。先把数据调整一下：让 $a$ 是较小的一方，并特判掉最开始 $b$ 就是 $a$ 的倍数的情况。抠完了边角情况之后，我们再来考虑这个题应该怎么做：根据实际的题目情况来划分：
①假设当前的局面是 $b - a < a$ ，即 $b$ 里最多再删掉一个 $a$ （注意这里是最小的情况了，因为如果连一个 $a$ 都没有就不可能有 $b > a$ ）。这个时候由于 $a \nmid b$ 所以 $(b - a) \nmid a$ ，也就是说如果走下去的话根本没有任何选择的余地了。只要下一步是必败态上一步就一定是必胜态。
②假设当前的局面是 $b - a > a$ ，即 $b$ 里可以去掉很多个 $a$ ，设 $x$ 是最大的，能使 $b - a * x <a$ 的正整数，即退到第一种情况的数 $x$ 。那么如果退过去的状态是必败态的话，前面的就一定是必胜态了。
如果反过来，退过去的状态是必胜态的话，现在这个局面还有退回的余地吗？答案是有的，如果说我当前不挪掉 $x$ 个石子，我选择挪掉 $x-1$ 个石子，那么剩下的这个局面给对手，对手只能是把刚刚没挪的那一个石子挪掉，于是对手就走到了一个必败态，因此必胜。
综上，②情况在理想情况下是必胜的。因为一旦走到①状态，局面就完全固定。而②局面转到①的时候是可以人为操作使得必胜的。故两个人中，谁先走到②状态谁就赢了，由于先手是Stan，具体代码里做一下交换就行了。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int a,b;
	while(scanf("%d%d",&a,&b),a || b)
	{
		int win = 1;
		while(1)
		{
			if(a > b)	swap(a,b);
			if(b % a == 0)	break;
			if(b - a > a)	break;
			
			b -= a;
			win ^= 1;
		}
		if(win)	puts("Stan wins");
		else puts("Ollie wins");
	}
    return 0;
}

③Nim游戏
题目链接：https://www.luogu.com.cn/problem/P2197
题目大意：有 $n$ 堆石子，每堆石子有 $a_i$ 个，现在Alice和Bob分别在每堆非空的石子里选出至少一颗石子，A先手，当没有石子拿的时候输。问谁会获胜。
数据范围： $n \leq 10000$

当所有的石子的个数异或起来不为 $0$ 的时候，Alice获胜
这个题的结论是很多人都知道的，学了博弈论基本开头就是这个。这里把这个结论简单证明一下：
首先，如果所有的石子都是 $0$ ，则显然是一个必败态。且显然异或和是 $0$ 。
当异或和不是 $0$ 的时候，把所有数变成二进制，在里面找到最高的一位 $1$ ，取 $1$ 就可以使整个局面的异或和变成 $0$ 且一定可以这么操作。故从一个非 $0$ 的状态一定可以转到一个全 $0$ 的状态。
对于全 $0$ 的状态来说，由于至少选出一个，所以必然走到一个非 $0$ 的状态。故只要起始是非 $0$ 的就一定是Alice胜利。

④[POJ 1704]Georigia and Bob
题目链接：http://poj.org/problem?id=1704
Georigia和Bob在玩一个游戏：有横向的一个棋盘上放着 $n$ 个棋子，第 $i$ 个棋子在 $p_i$ 的位置上，每次操作可以让每个棋子向左移动若干个格子，但是不可以跨过其他的棋子。当无法移动时输掉游戏。
数据范围：
$1 \leq n \leq 1000$
$1 \leq p_i \leq 10000$

这个题乍看上去没什么突破口，因为条件很奇怪，给的决策的限制条件只有说不能跨过某个棋子，但是又可以往左右两边动，这就导致看起来跟之前的 $NIM$ 游戏等博弈论的结论没什么关系，而且也不太好做， $dp$ 做起来好像也不太好办。还是得从题目的性质入手，可以发现说两个相邻的棋子之间既然不能相互跨越，那我把两个棋子看成是一组，转换一下这个问题：
先看棋子是偶数的情况，这种情况比较好想，如果是正确的再考虑奇数情况。
假如说现在把两两棋子看做是一个整体的话，对应到上一个 $NIM$ 游戏里就是一堆石子，里面的个数就是两个石子之间的距离：距离缩小等价于减少石块，距离增大等价于增加石块。现在来验证一下这个转换是不是跟上一问的 $NIM$ 游戏是等价的：如果把距离缩小的话就是减少石块，这显然就是上面的 $NIM$ 游戏里的操作。如果反过来就是增加石块，在对手增加石块的时候，只要镜像的也减少石块，那么状态就不会有任何变化。于是胜负态还是一一对应的，因此这个转换是和 $NIM$ 游戏完全一样的。
奇数个时，只要把第一位石头看做是和最左边的 $0$ 号点有配对就可以了。
最后结论的判断就和 $NIM$ 游戏一样，只要求出所有的距离最后异或就是判据了。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1005;
int a[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		for(int i = 0;i < n;++i)	scanf("%d",&a[i]);
		if(n & 1)	a[n++] = 0;
		sort(a ,a + n);
		int res = 0;
		for(int i = 0;i < n - 1;i += 2)
			res ^= (a[i + 1] - a[i] - 1);
		if(res)	puts("Georgia will win");
		else puts("Bob will win");
    }
    return 0;
}

感谢您的支持，我会继续努力的!